Search

The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in $1975$ by Pippenger and Golumbic. In $2017$, Czabarka, Sz\'ekely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and inducibilities of such trees. Following up on their work, we apply Razborov's flag algebra theory to this setting, introducing the flag algebra of rooted leaf-labeled binary trees. This framework allows us to use polynomial optimization methods, based on semidefinite programming, to efficiently obtain new upper bounds for the inducibility of trees and to improve existing ones. Additionally, we obtain the first outer approximations of profiles of trees, which represent all possible simultaneous densities of a pair of trees. Finally, we are able to prove the non-convexity of some of these profiles.

We consider the set of extremal points of the generalized unit ball induced by gradient total variation seminorms for vector-valued functions on bounded Euclidean domains. These extremal points are central to the understanding of sparse solutions and sparse optimization algorithms for variational regularization problems posed among such functions. For not fully vectorial cases in which either the domain or the target are one dimensional, or the sum of the total variations of each component is used, we prove that these extremals are fully characterized as in the scalar-valued case, that is, they consist of piecewise constant functions with two regions. For definitions involving more involved matrix norms and in particular spectral norms, which are of interest in image processing, we produce families of examples to show that the resulting set of extremal points is larger and includes piecewise constant functions with more than two regions. We also consider the total deformation induced by the symmetrized gradient, for which minimization with linear constraints appears in problems of determination of limit loads in a number of continuum mechanical models involving plasticity, bringing relevance to the corresponding extremal points. For this case, we show piecewise infinitesimally rigid functions with two pieces to be extremal under mild assumptions. Finally, as an example of an extremal which is not piecewise constant, we prove that unit radial vector fields are extremal for the Frobenius total variation in the plane., Comment: 33 pages, 0 figures

We show that solutions to the popular convex matrix LASSO problem (nuclear-norm--penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained optimization approaches. Specifically, we show that if (a) the ground truth matrix has low rank, (b) the (linear) measurement operator has the matrix restricted isometry property (RIP), and (c) the measurement error is small enough relative to the nuclear norm penalty, then the (unique) LASSO solution has rank (approximately) bounded by that of the ground truth. From this, we show (a) that a low-rank--projected proximal gradient descent algorithm will converge linearly to the LASSO solution from any initialization, and (b) that the nonconvex landscape of the low-rank Burer-Monteiro--factored problem formulation is benign in the sense that all second-order critical points are globally optimal and yield the LASSO solution.

We consider the controllability problem for the continuity equation where the dynamics is governed by a driftless control-affine system. Under suitable regularity conditions, the controllability of the system is a sufficient condition for the controllability of the continuity equation by means of time-varying feedback controls. Moreover, we show that there exist controls such that the flow of the control system is the optimal transport map, for the 2-Wasserstein distance, between two given probability measures.

The paper explores the use of dynamic adaptation gain/step size (DAG) for improving the adaptation transient performance of variable step-size LMS (VS-LMS) adaptation algorithms. A generic form for the implementation of the DAG within the VS-LMS algorithms is provided. The properties of the VS-LMS algorithms using dynamic adaptation gain are discussed in detail. Stability issues in deterministic environment and convergence properties in stochastic environment are examined. A transient performance analysis is proposed. Criteria for the selection of the coefficients of the DAG filter are provided.The potential of the VS-LMS adaptation algorithms using a DAG is then illustrated by simulation results (adaptive line enhancer, filter identification) and experimental results obtained on a relevant adaptive active noise attenuation system., Comment: arXiv admin note: substantial text overlap with arXiv:2403.13381

The article presents a new method of linear programming, called the surface movement method. This method constructs an optimal objective path on the surface of the feasible polytope from the initial boundary point to the point at which the optimal value of the objective function is achieved. The optimality of the path means moving in the direction of maximum increase/decrease in the value of the objective function. A formal description of the algorithm implementing the surface movement method is described. The convergence theorem of this algorithm is proved. The presented method can be effectively implemented using a feed forward deep neural network to determine the optimal direction of movement along the faces of the feasible polytope. To do this, a multidimensional local image of the linear programming problem is constructed at the point of the current approximation. This image is fed to the input of the deep neural network, which returns a vector determining the direction of the optimal objective path on the polytope surface.

In this paper, we explore a class of constrained saddle point problems with a bilevel structure, where the upper-level objective function is nonconvex-concave and smooth subject to a strongly convex lower-level objective function. This class of problems finds wide applicability in machine learning, including robust multi-task learning, adversarial learning, and robust meta-learning. While some studies have focused on simpler formulations, e.g., when the upper-level objective function is linear in the maximization component, there remains a significant gap in developing efficient projection-free and projection-based algorithms with theoretical guarantees for more general settings. To bridge this gap, we propose efficient single-loop one-sided projection-free, and fully projection-based primal-dual methods. By leveraging regularization and nested approximation techniques, we initially devise a bilevel primal-dual one-sided projection-free algorithm, requiring $\mathcal{O}(\epsilon^{-4})$ iterations to attain an $\epsilon$-stationary point. Subsequently, we develop a bilevel primal-dual fully projected algorithm, capable of achieving an $\epsilon$-stationary solution within $\mathcal{O}(\epsilon^{-5})$ iterations. To the best of our knowledge, our proposed algorithms represent among the first methods for solving general non-bilinear saddle point problems with a bilevel structure.

We study online policy optimization in nonlinear time-varying dynamical systems where the true dynamical models are unknown to the controller. This problem is challenging because, unlike in linear systems, the controller cannot obtain globally accurate estimations of the ground-truth dynamics using local exploration. We propose a meta-framework that combines a general online policy optimization algorithm ($\texttt{ALG}$) with a general online estimator of the dynamical system's model parameters ($\texttt{EST}$). We show that if the hypothetical joint dynamics induced by $\texttt{ALG}$ with known parameters satisfies several desired properties, the joint dynamics under inexact parameters from $\texttt{EST}$ will be robust to errors. Importantly, the final policy regret only depends on $\texttt{EST}$'s predictions on the visited trajectory, which relaxes a bottleneck on identifying the true parameters globally. To demonstrate our framework, we develop a computationally efficient variant of Gradient-based Adaptive Policy Selection, called Memoryless GAPS (M-GAPS), and use it to instantiate $\texttt{ALG}$. Combining M-GAPS with online gradient descent to instantiate $\texttt{EST}$ yields (to our knowledge) the first local regret bound for online policy optimization in nonlinear time-varying systems with unknown dynamics.

This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables. The objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a "prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of "prophet inequalities." In this paper we characterize sharp prophet inequalities for single threshold stopping rules as solutions to infinite two person zero sum games on the unit square with special payoff kernels. The proposed game theoretic characterization allows one to derive sharp non-asymptotic prophet inequalities for different classes of distributions. This, in turn, gives rise to a simple and computationally tractable algorithmic paradigm for deriving optimal single threshold stopping rules. Our results also indicate that several classical observations in the literature are either incorrect or incomplete in treating this problem.

We introduce a framework rooted in a rate distortion problem for Markov chains, and show how a suite of commonly used Markov Chain Monte Carlo (MCMC) algorithms are specific instances within it, where the target stationary distribution is controlled by the distortion function. Our approach offers a unified variational view on the optimality of algorithms such as Metropolis-Hastings, Glauber dynamics, the swapping algorithm and Feynman-Kac path models. Along the way, we analyze factorizability and geometry of multivariate Markov chains. Specifically, we demonstrate that induced chains on factors of a product space can be regarded as information projections with respect to a particular divergence. This perspective yields Han--Shearer type inequalities for Markov chains as well as applications in the context of large deviations and mixing time comparison., Comment: 63 pages, 6 figures

We consider the problem of finding curves of minimum pointwise-maximum curvature, i.e., curves of minimax curvature, among planar curves of fixed length with prescribed endpoints and tangents at the endpoints. We reformulate the problem in terms of optimal control and use the maximum principle, as well as some geometrical arguments, to produce a classification of the types of solutions. Using the classification, we devise a numerical method which reduces the infinite-dimensional optimization problem to a finite-dimensional problem with just six variables. The solution types, together with some further observations on optimality, are illustrated via numerical examples.

Repeated decision-making problems under uncertainty may arise in the health policy context, such as infectious disease control for COVID-19 and other epidemics. These problems may sometimes be effectively solved using Markov decision processes (MDPs). However, the continuous or large state space of such problems for capturing infectious disease prevalence renders it difficult to implement tractable MDPs to identify the optimal disease control policy over time. We therefore develop an algorithm for discretizing continuous states for approximate MDP solutions in this context. We benchmark performance against a uniform discretization using both a synthetic example and an example of COVID-19 in Los Angeles County.

This paper presents a distributed model predictive control (DMPC) algorithm for a heterogeneous platoon using arbitrary communication topologies, as long as each vehicle is able to communicate with a preceding vehicle in the platoon. The proposed DMPC algorithm is able to accommodate any spacing policy that is affine in a vehicle's velocity, which includes constant distance or constant time headway spacing policies. By analyzing the total cost for the entire platoon, a sufficient condition is derived to guarantee platoon asymptotic stability. Simulation experiments with a platoon of 50 vehicles and hardware experiments with a platoon of four 1/10th scale vehicles validate the algorithm and compare performance under different spacing policies and communication topologies.

The $k$-parity problem is a classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, we solve the $k$-parity problem with stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that SGD can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube ($k\le O(\sqrt{d})$) with a sample complexity of $\tilde{O}(d^{k-1})$ using $2^{\Theta(k)}$ neurons, thus matching the established $\Omega(d^{k})$ lower bounds of Statistical Query (SQ) models. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the $k$-parity problem. We then demonstrate how a trained neural network with SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors. Our theoretical results and findings are supported by empirical evidence, showcasing the efficiency and efficacy of our approach., Comment: 36 pages, 7 figures, 3 tables

A general theory of stochastic decision forests reconciling two concepts of information flow -- decision trees and refined partitions on the one hand, filtrations from probability theory on the other -- is constructed. The traditional "nature" agent is replaced with a one-shot lottery draw that determines a tree of a given decision forest, while each "personal" agent is equipped with an oracle providing updates on the draw's result and makes partition refining choices adapted to this information. This theory overcomes the incapacity of existing approaches to extensive form theory to capture continuous time stochastic processes like Brownian motion as outcomes of "nature" decision making in particular. Moreover, a class of stochastic decision forests based on paths of action indexed by time is constructed, covering a large fraction of models from the literature and constituting a first step towards an approximation theory for stochastic differential games in extensive form., Comment: 32 pages (47 pages with appendix), 4 figures, first part of a three-paper series

We study minimax optimization problems defined over infinite-dimensional function classes. In particular, we restrict the functions to the class of overparameterized two-layer neural networks and study (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural network. As an initial step, we consider the minimax optimization problem stemming from estimating a functional equation defined by conditional expectations via adversarial estimation, where the objective function is quadratic in the functional space. For this problem, we establish convergence under the mean-field regime by considering the continuous-time and infinite-width limit of the optimization dynamics. Under this regime, gradient descent-ascent corresponds to a Wasserstein gradient flow over the space of probability measures defined over the space of neural network parameters. We prove that the Wasserstein gradient flow converges globally to a stationary point of the minimax objective at a $\mathcal{O}(T^{-1} + \alpha^{-1} ) $ sublinear rate, and additionally finds the solution to the functional equation when the regularizer of the minimax objective is strongly convex. Here $T$ denotes the time and $\alpha$ is a scaling parameter of the neural network. In terms of representation learning, our results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $\mathcal{O}(\alpha^{-1})$, measured in terms of the Wasserstein distance. Finally, we apply our general results to concrete examples including policy evaluation, nonparametric instrumental variable regression, and asset pricing., Comment: 72 pages, submitted

Mirror Descent is a popular algorithm, that extends Gradients Descent (GD) beyond the Euclidean geometry. One of its benefits is to enable strong convergence guarantees through smooth-like analyses, even for objectives with exploding or vanishing curvature. This is achieved through the introduction of the notion of relative smoothness, which holds in many of the common use-cases of Mirror descent. While basic deterministic results extend well to the relative setting, most existing stochastic analyses require additional assumptions on the mirror, such as strong convexity (in the usual sense), to ensure bounded variance. In this work, we revisit Stochastic Mirror Descent (SMD) proofs in the (relatively-strongly-) convex and relatively-smooth setting, and introduce a new (less restrictive) definition of variance which can generally be bounded (globally) under mild regularity assumptions. We then investigate this notion in more details, and show that it naturally leads to strong convergence guarantees for stochastic mirror descent. Finally, we leverage this new analysis to obtain convergence guarantees for the Maximum Likelihood Estimator of a Gaussian with unknown mean and variance.

In the context of the optimization of rotating electric machines, many different objective functions are of interest and considering this during the optimization is of crucial importance. While evolutionary algorithms can provide a Pareto front straightforwardly and are widely used in this context, derivative-based optimization algorithms can be computationally more efficient. In this case, a Pareto front can be obtained by performing several optimization runs with different weights. In this work, we focus on a free-form shape optimization approach allowing for arbitrary motor geometries. In particular, we propose a way to efficiently obtain Pareto-optimal points by moving along to the Pareto front exploiting a homotopy method based on second order shape derivatives., Comment: 9 pages, 3 figures. SCEE2024 conference proceeding paper

We consider the topology optimization problem of a 2d permanent magnet synchronous machine in magnetostatic operation with demagnetization. This amounts to a PDE-constrained multi-material design optimization problem with an additional pointwise state constraint. Using a generic framework we can incorporate this additional constraint and compute the corresponding topological derivative. We present and discuss optimization results obtained by a multi-material level set algorithm., Comment: 9 pages, 3 figures

This investigation is dedicated to a two-player zero-sum stochastic differential game (SDG), where a cost function is characterized by a backward stochastic differential equation (BSDE) with a continuous and monotonic generator regarding the first unknown variable, which possesses immense applicability in financial engineering. A verification theorem by virtue of classical solution of derived Hamilton-Jacobi-Bellman-Isaacs (HJBI) equation is given. The dynamic programming principle (DPP) and unique weak (viscosity) solvability of HJBI equation are formulated through comparison theorem for BSDEs with monotonic generators and stability of viscosity solution. Some new regularity properties of value function are presented. Finally, we propose three concrete examples, which are concerned with resp., classical, and viscosity solution of HJBI equation, as well as a financial application where an investor with a non-Lipschitzian Epstein-Zin utility deals with market friction to maximize her utility preference.

This paper focuses on multi-agent stochastic differential games for jump-diffusion systems. On one hand, we study the multi-agent game for optimal investment in a jump-diffusion market. We derive constant Nash equilibria and provide sufficient conditions for their existence and uniqueness for exponential, power, and logarithmic utilities, respectively. On the other hand, we introduce a computational framework based on the actor-critic method in deep reinforcement learning to solve the stochastic control problem with jumps. We extend this algorithm to address the multi-agent game with jumps and utilize parallel computing to enhance computational efficiency. We present numerical examples of the Merton problem with jumps, linear quadratic regulators, and the optimal investment game under various settings to demonstrate the accuracy, efficiency, and robustness of the proposed method. In particular, neural network solutions numerically converge to the derived constant Nash equilibrium for the multi-agent game.

In this paper, we present a novel derivative-free optimization framework for solving unconstrained stochastic optimization problems. Many problems in fields ranging from simulation optimization to reinforcement learning involve settings where only stochastic function values are obtained via an oracle with no available gradient information, necessitating the usage of derivative-free optimization methodologies. Our approach includes estimating gradients using stochastic function evaluations and integrating adaptive sampling techniques to control the accuracy in these stochastic approximations. We consider various gradient estimation techniques including standard finite difference, Gaussian smoothing, sphere smoothing, randomized coordinate finite difference, and randomized subspace finite difference methods. We provide theoretical convergence guarantees for our framework and analyze the worst-case iteration and sample complexities associated with each gradient estimation method. Finally, we demonstrate the empirical performance of the methods on logistic regression and nonlinear least squares problems.

We consider stochastic optimization problems with functional constraints. If the objective and constraint functions are not convex, the classical stochastic approximation algorithms such as the proximal stochastic gradient descent do not lead to efficient algorithms. In this work, we put forth an accelerated SCA algorithm that utilizes the recursive momentum-based acceleration which is widely used in the unconstrained setting. Remarkably, the proposed algorithm also achieves the optimal SFO complexity, at par with that achieved by state-of-the-art (unconstrained) stochastic optimization algorithms and match the SFO-complexity lower bound for minimization of general smooth functions. At each iteration, the proposed algorithm entails constructing convex surrogates of the objective and the constraint functions, and solving the resulting convex optimization problem. A recursive update rule is employed to track the gradient of the objective function, and contributes to achieving faster convergence and improved SFO complexity. A key ingredient of the proof is a new parameterized version of the standard Mangasarian-Fromowitz Constraints Qualification, that allows us to bound the dual variables and hence establish that the iterates approach an $\epsilon$-stationary point. We also detail a obstacle-avoiding trajectory optimization problem that can be solved using the proposed algorithm, and show that its performance is superior to that of the existing algorithms. The performance of the proposed algorithm is also compared against that of a specialized sparse classification algorithm on a binary classification problem., Comment: 32 pages, 4 figures, journal submission

For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact. The aim of the presented sequential mixed-integer quadratic programming (MIQP) algorithm for mixed-integer nonlinear problems (MINLPs) is to extend the SQP/SCP methodology to MINLPs and leverage the availability of efficient MIQP solvers. The algorithm employs a three-step method in each iterate: First, the MINLP is linearized at a given iterate. Second, an MIQP with its feasible set restricted to a specific region around the current linearization point is formulated and solved. Third, the integer variables obtained from the MIQP solution are fixed, and only an NLP in the continuous variables is solved. The outcome of the third step is compared to previous iterates, and the best iterate so far is used as a linearization point in the next iterate. Crucially, the objective values and derivatives from all previous iterates are used to formulate the polyhedral region in the second step. The linear inequalities that define the region build on concepts from generalized Benders' decomposition for MINLPs. Although the presented MINLP algorithm is a heuristic method without any global optimality guarantee, it converges to the exact integer solution when applied to convex MINLP with a linear outer structure. The conducted numerical experiments demonstrate that the proposed algorithm is competitive with other open-source solvers for MINLP. Finally, we solve two mixed-integer optimal control problems (MIOCPs) transcribed into MINLPs via direct methods, showing that the presented algorithm can effectively deal with nonlinear equality constraints, a major hurdle for generic MINLP solvers., Comment: Andrea Ghezzi and Wim Van Roy contributed equally to this work. 34 pages, 11 figures, 3 tables

Deep learning has been widely applied to solve partial differential equations (PDEs) in computational fluid dynamics. Recent research proposed a PDE correction framework that leverages deep learning to correct the solution obtained by a PDE solver on a coarse mesh. However, end-to-end training of such a PDE correction model over both solver-dependent parameters such as mesh parameters and neural network parameters requires the PDE solver to support automatic differentiation through the iterative numerical process. Such a feature is not readily available in many existing solvers. In this study, we explore the feasibility of end-to-end training of a hybrid model with a black-box PDE solver and a deep learning model for fluid flow prediction. Specifically, we investigate a hybrid model that integrates a black-box PDE solver into a differentiable deep graph neural network. To train this model, we use a zeroth-order gradient estimator to differentiate the PDE solver via forward propagation. Although experiments show that the proposed approach based on zeroth-order gradient estimation underperforms the baseline that computes exact derivatives using automatic differentiation, our proposed method outperforms the baseline trained with a frozen input mesh to the solver. Moreover, with a simple warm-start on the neural network parameters, we show that models trained by these zeroth-order algorithms achieve an accelerated convergence and improved generalization performance.

Contraction theory is a mathematical framework for studying the convergence, robustness, and modularity properties of dynamical systems and algorithms. In this opinion paper, we provide five main opinions on the virtues of contraction theory. These opinions are (i) contraction theory is a unifying framework emerging from classical and modern works, (ii) contractivity is computationally-friendly, robust, and modular stability, (iii) numerous dynamical systems are contracting, (iv) contraction theory is relevant to modern applications, and (v) contraction theory can be vastly extended in numerous directions. We survey recent theoretical and applied research in each of these five directions.

Mean field games (MFGs) model equilibria in games with a continuum of weakly interacting players as limiting systems of symmetric $n$-player games. We consider the finite-state, infinite-horizon problem with ergodic cost. Assuming Markovian strategies, we first prove that any solution to the MFG system gives rise to a $(C/\sqrt{n})$-Nash equilibrium in the $n$-player game. We follow this result by proving the same is true for the strategy profile derived from the master equation. We conclude the main theoretical portion of the paper by establishing a large deviation principle for empirical measures associated with the asymptotic Nash equilibria. Then, we contrast the asymptotic Nash equilibria using an example. We solve the MFG system directly and numerically solve the ergodic master equation by adapting the deep Galerkin method of Sirignano and Spiliopoulos. We use these results to derive the strategies of the asymptotic Nash equilibria and compare them. Finally, we derive an explicit form for the rate functions in dimension two.

Meta-analysis allows rigorous aggregation of estimates and uncertainty across multiple studies. When a given study reports multiple estimates, such as log odds ratios (ORs) or log relative risks (RRs) across exposure groups, accounting for within-study correlations improves accuracy and efficiency of meta-analytic results. Canonical approaches of Greenland-Longnecker and Hamling estimate pseudo cases and non-cases for exposure groups to obtain within-study correlations. However, currently available implementations for both methods fail on simple examples. We review both GL and Hamling methods through the lens of optimization. For ORs, we provide modifications of each approach that ensure convergence for any feasible inputs. For GL, this is achieved through a new connection to entropic minimization. For Hamling, a modification leads to a provably solvable equivalent set of equations given a specific initialization. For each, we provide implementations a guaranteed to work for any feasible input. For RRs, we show the new GL approach is always guaranteed to succeed, but any Hamling approach may fail: we give counter-examples where no solutions exist. We derive a sufficient condition on reported RRs that guarantees success when reported variances are all equal., Comment: 31 pages, 9 figures

Wildfires ignited by power systems infrastructure are among the most destructive wildfires; hence some utility companies in wildfire-prone regions have pursued a proactive policy of emergency power shutoffs. These shutoffs, while mitigating the risk of disastrous ignition events, result in power outages that could negatively impacts vulnerable communities. In this paper, we consider how to equitably allocate funds to underground and effectively de-risk power lines in transmission networks. We explore the impact of the 2021 White House resource allocation policy called the Justice40 initiative, which states that 40% of the benefits of federally-funded climate-related investments should go to socially vulnerable communities. The definition of what constitutes a vulnerable community varies by organization, and we consider two major recently proposed vulnerability indices: the Justice40 index created under the 2021 White House and the Social Vulnerability Index (SVI) developed by the Center for Disease Control and Prevention (CDC). We show that allocating budget according to these two indices fails to reduce power outages for indigenous communities and those subject to high wildfire ignition risk using a high-fidelity synthetic power grid dataset that matches the key features of the Texas transmission system. We discuss how aggregation of communities and "one size fits all" vulnerability indices might be the reasons for the misalignment between the goals of vulnerability indices and their realized impact in this particular case study. We provide a method of achieving an equitable investment plan by adding group-level protections on percentage of load that is shed across each population group of interest.

We investigate the optimal reinsurance problem in the risk model with jump clustering features introduced in [7]. This modeling framework is inspired by the concept initially proposed in [15], combining Hawkes and Cox processes with shot noise intensity models. Specifically, these processes describe self-exciting and externally excited jumps in the claim arrival intensity, respectively. The insurer aims to maximize the expected exponential utility of terminal wealth for general reinsurance contracts and reinsurance premiums. We discuss two different methodologies: the classical stochastic control approach based on the Hamilton-Jacobi-Bellman (HJB) equation and a backward stochastic differential equation (BSDE) approach. In a Markovian setting, differently from the classical HJB-approach, the BSDE method enables us to solve the problem without imposing any requirements for regularity on the associated value function. We provide a Verification Theorem in terms of a suitable BSDE driven by a two-dimensional marked point process and we prove an existence result relaying on the theory developed in [27] for stochastic Lipschitz generators. After discussing the optimal strategy for general reinsurance contracts and reinsurance premiums, we provide more explicit results in some relevant cases. Finally, we provide comparison results that highlight the heightened risk stemming from the self-exciting component in contrast to the externally-excited counterpart and discuss the monotonicity property of the value function., Comment: 40 pages

This thesis proposes an adaptive linearized alternating direction multiplier method to improve the convergence rate of the algorithm by using adaptive techniques to dynamically select the regular term coefficients. The innovation of this method is to utilize the information of the current iteration point to adaptively select the appropriate parameters, thus expanding the selection of the subproblem step size and improving the convergence rate of the algorithm while ensuring convergence.The advantage of this method is that it can improve the convergence rate of the algorithm as much as possible without compromising the convergence. This is very beneficial for the solution of optimization problems because the traditional linearized alternating direction multiplier method has a trade-off in the selection of the regular term coefficients: larger coefficients ensure convergence but tend to lead to small step sizes, while smaller coefficients allow for an increase in the iterative step size but tend to lead to the algorithm's non-convergence. This balance can be better handled by adaptively selecting the parameters, thus improving the efficiency of the algorithm.Overall, the method proposed in this thesis is of great importance in the field of matrix optimization and has a positive effect on improving the convergence speed and efficiency of the algorithm. It is hoped that this adaptive idea can bring new inspiration to the development of the field of matrix optimization and promote the research and application in related fields.

A novel approach for creating tool paths for continuous carbon fiber-reinforced thermoplastic 3D printing is introduced. The aim is to enable load-bearing connections while avoiding non-manufacturable crossings of paths by generating layer specific patterns. We require a graph representation of the structural design with given desired continuous fiber connections. From this, optimal fiber patterns are obtained for each printing layer by solving linear integer optimization problems. Each layer may have a unique solution based on the history of the previous layers. Additionally, a path planning approach is presented which interprets the obtained layers via curves based on quadratic and cubic B\'ezier splines and their offset curves in constant distance. The single parameter for the construction of the paths is the minimal turning radius of the fibers. The path planning provides a new interpretation for the final geometry of the design to be printed., Comment: 29 pages (single column), 29 figures

With the outstanding performance of policy gradient (PG) method in the reinforcement learning field, the convergence theory of it has aroused more and more interest recently. Meanwhile, the significant importance and abundant theoretical researches make the stochastic linear quadratic (SLQ) control problem a starting point for studying PG in model-based learning setting. In this paper, we study the PG method for the SLQ problem in infinite horizon and take a step towards providing rigorous guarantees for gradient methods. Although the cost functional of linear-quadratic problem is typically nonconvex, we still overcome the difficulty based on gradient domination condition and L-smoothness property, and prove exponential/linear convergence of gradient flow/descent algorithm.

Many stochastic algorithms have been proposed to solve the bilevel optimization problem, where the lower level function is strongly convex and the upper level value function is nonconvex. In particular, exising Hessian inverse-free algorithms that utilize momentum recursion or variance reduction technqiues can reach an $\epsilon$-stationary point with a complexity of $\tilde{O}(\epsilon^{-1.5})$ under usual smoothness conditions. However, $\tilde{O}(\epsilon^{-1.5})$ is a complexity higher than $O(\epsilon^{-1.5})$. How to make a Hessian inverse-free algorithm achieve the complexity of $O(\epsilon^{-1.5})$ under usual smoothness conditions remains an unresolved problem. In this paper, we propose a new Hessian inverse-free algorithm based on the projected stochastic gradient descent method and variance reduction technique of SPIDER. This algorithm can achieve a complexity of $O(\epsilon^{-1.5})$ under usual smoothness conditions whether it runs in a fully single loop or double loop structure. Finally, we validate our theoretical results through synthetic experiments and demonstrate the efficiency of our algorithm in some machine learning applications.

This paper considers a distributed adaptive optimization problem, where all agents only have access to their local cost functions with a common unknown parameter, whereas they mean to collaboratively estimate the true parameter and find the optimal solution over a connected network. A general mathematical framework for such a problem has not been studied yet. We aim to provide valuable insights for addressing parameter uncertainty in distributed optimization problems and simultaneously find the optimal solution. Thus, we propose a novel Prediction while Optimization scheme, which utilizes distributed fractional Bayesian learning through weighted averaging on the log-beliefs to update the beliefs of unknown parameters, and distributed gradient descent for renewing the estimation of the optimal solution. Then under suitable assumptions, we prove that all agents' beliefs and decision variables converge almost surely to the true parameter and the optimal solution under the true parameter, respectively. We further establish a sublinear convergence rate for the belief sequence. Finally, numerical experiments are implemented to corroborate the theoretical analysis., Comment: 16 pages, 6 figures

We develop a switched predictor-feedback law, which achieves global asymptotic stabilization of linear systems with input delay and with the plant and actuator states available only in (almost) quantized form. The control design relies on a quantized version of the nominal predictor-feedback law for linear systems, in which quantized measurements of the plant and actuator states enter the predictor state formula. A switching strategy is constructed to dynamically adjust the tunable parameter of the quantizer (in a piecewise constant manner), in order to initially increase the range and subsequently decrease the error of the quantizers. The key element in the proof of global asymptotic stability in the supremum norm of the actuator state is derivation of solutions' estimates combining a backstepping transformation with small-gain and input-to-state stability arguments, for addressing the error due to quantization. We extend this result to the input quantization case and illustrate our theory with a numerical example., Comment: 12 pages, 7 figures, submitted to Systems & Control Letters

The zonotope containment problem, i.e., whether one zonotope is contained in another, is a central problem in control theory to compute invariant sets, obtain fixed points of reachable sets, detect faults, and robustify controllers. Despite the inherent co-NP-hardness of this problem, an approximation algorithm developed by S. Sadraddini and R. Tedrake has gained widespread recognition for its swift execution and consistent reliability in practical scenarios. In our study, we substantiate the precision of the algorithm with a definitive proof, elucidating the empirical accuracy observed in practice. Our proof hinges on establishing a connection between the containment problem and the computation of matrix norms, thereby enabling the extension of the approximation algorithm to encompass ellipsotopes, a broader class of sets derived from zonotopes. Moreover, we explore the computational complexity of the ellipsotope containment problem, focusing on approximability. Finally, we present new methods to calculate robust control invariant sets for linear dynamical systems, demonstrating the practical relevance of approximations to the ellipsotope containment problem.

Active solids are a large class of materials, including both living soft tissues and artificial matter, that share the ability to undergo strain even in absence of external loads. While in engineered materials the actuation is typically designed a priori, in natural materials it is an unknown of the problem. In such a framework, the identification of inactive regions in active materials is of particular interest. An example of paramount relevance is cardiac mechanics and the assessment of regions of the cardiac muscle with impaired contractility. The impossibility to measure the local active forces directly, suggests us to develop a novel methodology exploiting kinematic data from clinical images by a variational approach to reconstruct the local contractility in the cardiac muscle. Introducing a suitable cost functional and effective regularization methods, we minimize the discrepancy between observed and simulated displacement and we recover the contractility map of the muscle. Numerical experiments, including severe conditions with added noise to model uncertainties, and data knowledge limited to the boundary, demonstrate the effectiveness of our approach. Unlike other methods, we provide a spatially continuous recovery of the contractility map at a low computational cost., Comment: 19 pages, 12 figures

Since infectious pathogens start spreading into a susceptible population, mathematical models can provide policy makers with reliable forecasts and scenario analyses, which can be concretely implemented or solely consulted. In these complex epidemiological scenarios, machine learning architectures can play an important role, since they directly reconstruct data-driven models circumventing the specific modelling choices and the parameter calibration, typical of classical compartmental models. In this work, we discuss the efficacy of Kernel Operator Learning (KOL) to reconstruct population dynamics during epidemic outbreaks, where the transmission rate is ruled by an input strategy. In particular, we introduce two surrogate models, named KOL-m and KOL-$\partial$, which reconstruct in two different ways the evolution of the epidemics. Moreover, we evaluate the generalization performances of the two approaches with different kernels, including the Neural Tangent Kernels, and compare them with a classical neural network model learning method. Employing synthetic but semi-realistic data, we show how the two introduced approaches are suitable for realizing fast and robust forecasts and scenario analyses, and how these approaches are competitive for determining optimal intervention strategies with respect to specific performance measures., Comment: 39 pages, 13 figures

Recently, the proximal Newton-type method and its variants have been generalized to solve composite optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. In this paper, we propose an adaptive quadratically regularized proximal quasi-Newton method, named ARPQN, to solve this class of problems. Under some mild assumptions, the global convergence, the local linear convergence rate and the iteration complexity of ARPQN are established. Numerical experiments and comparisons with other state-of-the-art methods indicate that ARPQN is very promising. We also propose an adaptive quadratically regularized proximal Newton method, named ARPN. It is shown the ARPN method has a local superlinear convergence rate under certain reasonable assumptions, which demonstrates attractive convergence properties of regularized proximal Newton methods., Comment: 38 pages, 6 figures

We provide the first known algorithm that provably achieves $\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$ function evaluations for the discounted discrete-time LQR problem with unknown parameters, without relying on two-point gradient estimates. These estimates are known to be unrealistic in many settings, as they depend on using the exact same initialization, which is to be selected randomly, for two different policies. Our results substantially improve upon the existing literature outside the realm of two-point gradient estimates, which either leads to $\widetilde{\mathcal{O}}(1/\varepsilon^2)$ rates or heavily relies on stability assumptions.

We introduce Geometric Neural Operators (GNPs) for accounting for geometric contributions in data-driven deep learning of operators. We show how GNPs can be used (i) to estimate geometric properties, such as the metric and curvatures, (ii) to approximate Partial Differential Equations (PDEs) on manifolds, (iii) learn solution maps for Laplace-Beltrami (LB) operators, and (iv) to solve Bayesian inverse problems for identifying manifold shapes. The methods allow for handling geometries of general shape including point-cloud representations. The developed GNPs provide approaches for incorporating the roles of geometry in data-driven learning of operators.

With the success of deep neural networks (NNs) in a variety of domains, the computational and storage requirements for training and deploying large NNs have become a bottleneck for further improvements. Sparsification has consequently emerged as a leading approach to tackle these issues. In this work, we consider a simple yet effective approach to sparsification, based on the Bridge, or $L_p$ regularization during training. We introduce a novel weight decay scheme, which generalizes the standard $L_2$ weight decay to any $p$ norm. We show that this scheme is compatible with adaptive optimizers, and avoids the gradient divergence associated with $0

In this study, we present a novel swarm-based approach for generating optimized stress-aligned trajectories for 3D printing applications. The method utilizes swarming dynamics to simulate the motion of virtual agents along the stress produced in a loaded part. Agent trajectories are then used as print trajectories. With this approach, the complex global trajectory generation problem is subdivided into a set of sequential and computationally efficient quadratic programs. Through comprehensive evaluations in both simulation and experiments, we compare our method with state-of-the-art approaches. Our results highlight a remarkable improvement in computational efficiency, achieving a 115x faster computation speed than existing methods. This efficiency, combined with the possibility to tune the trajectories spacing to match the deposition process constraints, makes the potential integration of our approach into existing 3D printing processes seamless. Additionally, the open-hole tensile specimen produced on a conventional fused filament fabrication set-up with our algorithm achieve a notable ~10% improvement in specific modulus compared to existing trajectory optimization methods., Comment: To be submitted to IEEE Access

A key challenge in contrastive learning is to generate negative samples from a large sample set to contrast with positive samples, for learning better encoding of the data. These negative samples often follow a softmax distribution which are dynamically updated during the training process. However, sampling from this distribution is non-trivial due to the high computational costs in computing the partition function. In this paper, we propose an Efficient Markov Chain Monte Carlo negative sampling method for Contrastive learning (EMC$^2$). We follow the global contrastive learning loss as introduced in SogCLR, and propose EMC$^2$ which utilizes an adaptive Metropolis-Hastings subroutine to generate hardness-aware negative samples in an online fashion during the optimization. We prove that EMC$^2$ finds an $\mathcal{O}(1/\sqrt{T})$-stationary point of the global contrastive loss in $T$ iterations. Compared to prior works, EMC$^2$ is the first algorithm that exhibits global convergence (to stationarity) regardless of the choice of batch size while exhibiting low computation and memory cost. Numerical experiments validate that EMC$^2$ is effective with small batch training and achieves comparable or better performance than baseline algorithms. We report the results for pre-training image encoders on STL-10 and Imagenet-100., Comment: 20 pages

We consider toric maximum likelihood estimation over the field of Puiseux series and study critical points of the likelihood function using tropical methods. This problem translates to finding the intersection points of a tropical affine space with a classical linear subspace. We derive new structural results on tropical affine spaces and use these to give a complete and explicit description of the tropical critical points in certain cases. In these cases, we associate tropical critical points to the simplices in a regular triangulation of the polytope giving rise to the toric model., Comment: 20 pages, 7 figures

For the binary classification problem, a novel nonlinear kernel-free quadratic hyper-surface support vector machine with 0-1 loss function (QSSVM$_{0/1}$) is proposed. Specifically, the task of QSSVM$_{0/1}$ is to seek a quadratic separating hyper-surface to divide the samples into two categories. And it has better interpretability than the methods using kernel functions, since each feature of the sample acts both independently and synergistically. By introducing the 0-1 loss function to construct the optimization model makes the model obtain strong sample sparsity. The proximal stationary point of the optimization problem is defined by the proximal operator of the 0-1 loss function, which figures out the problem of non-convex discontinuity of the optimization problem due to the 0-1 loss function. A new iterative algorithm based on the alternating direction method of multipliers (ADMM) framework is designed to solve the optimization problem, which relates to the working set defined by support vectors. The computational complexity and convergence of the algorithm are discussed. Numerical experiments on 4 artificial datasets and 14 benchmark datasets demonstrate that our QSSVM$_{0/1}$ achieves higher classification accuracy, fewer support vectors and less CPU time cost than other state-of-the-art methods.

We study the continuous set covering problem on networks and propose several new MILP formulations and valid inequalities. In contrast to state-of-the-art formulations, the new formulations only use edges to index installed points, and the formulation sizes are smaller. The covering conditions can be represented as multivariate piecewise linear concave constraints, which we formulate as disjunctive systems. We propose three MILP formulations based on indicator constraint, big-M, and disjunctive programming techniques for modeling the disjunctive system. Finally, we give a classification of new and old formulations, and conduct experiments to compare them computationally., Comment: Submitted

We consider a game, in which the dynamics is described by a non-linear Volterra integral equation of Hammerstein type with a weakly-singular kernel and the goals of the first and second players are, respectively, to minimize and maximize a given cost functional. We propose a way of how the dynamic programming principle can be formalized and the theory of generalized (viscosity) solutions of path-dependent Hamilton--Jacobi equations can be developed in order to prove the existence of the game value, obtain a characterization of the value functional, and construct players' optimal feedback strategies.

In this paper, we study the eigenvalue problem of stochastic Hamiltonian system driven by Brownian motion and Markov chain with boundary conditions and time-dependent coefficients. For any dimensional case, the existence of the first eigenvalue is proven and the corresponding eigenfunctions are constructed by virtue of dual transformation and generalized Riccati equation system. Furthermore, we have more finely characterized the existence of all eigenvalues and constructed the related eigenfunctions for one-dimensional Hamiltonian system. Moreover, the increasing order of these eigenvalues have also been given., Comment: 22 pages